def max_subarray_prefix_sum(nums):
    # 初始化前缀和数组和变量
    pre_sum = 0
    start = 0
    end = 0
    tmp_sum = 0
    min_pre_sum = 0
    max_sum = nums[0]
    temp_start = 0
    for i , num in enumerate(nums):
        pre_sum += num
        if pre_sum - min_pre_sum > max_sum:
            max_sum = pre_sum - min_pre_sum
            start = temp_start
            end = i

        if pre_sum < min_pre_sum:
            min_pre_sum = pre_sum
            temp_start = i + 1

    return max_sum, nums[start:end+1]




def max_subarray(nums):
    # 初始化变量
    current_sum = max_sum = nums[0]
    start = end = temp_start = 0

    for i in range(1, len(nums)):
        if nums[i] > current_sum + nums[i]:
            # 如果当前元素大于当前和加上当前元素，重新开始子数组
            current_sum = nums[i]
            temp_start = i
        else:
            # 否则将当前元素加到当前子数组中
            current_sum += nums[i]

        # 如果找到了更大的子数组和，更新最大值和子数组的边界
        if current_sum > max_sum:
            max_sum = current_sum
            start = temp_start
            end = i

    # 返回最大子数组和和子数组
    return max_sum, nums[start:end + 1]


# 示例用法
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4, -20, 3]
max_sum, subarray = max_subarray(nums)
print('first we do with max_subarray(): ')
print("最大子数组的和:", max_sum)
print("最大子数组:", subarray)

max_sum, subarray = max_subarray_prefix_sum(nums)
print('the second edition we do with max_subarray_prefix_sum(): ')
print("最大子数组的和:", max_sum)
print("最大子数组:", subarray)
